package com.mokairui.linear;

import java.util.Iterator;

/**
 * @Description 顺序表
 * @Author Mokairui
 * @Since 2022/3/22
 */
public class SequenceList<T> implements Iterable<T> {
    // 存储元素的数组
    private T[] elements;
    // 记录当前顺序表中的元素个数
    private int counts;

    public SequenceList(int capacity) {
        elements = ((T[]) new Object[capacity]);
        counts = 0;
    }
    
    // 将一个线性表置为空表
    public void clear() {
        this.counts = 0;
    }
    
    // 判断当前线性表是否为空表
    public boolean isEmpty() {
        return counts == 0;
    }
    
    // 获取线性表的长度
    public int length() {
        return counts;
    }
    
    // 获取指定位置的元素
    public T get(int i) {
        return elements[i];
    }
    
    // 向线性表中添加元素t
    public void insert(T t) {
        if (counts == elements.length) {
            resize(2 * elements.length);
        }
        elements[counts++] = t;
    }
    
    // 在i元素处插入元素t
    public void insert(T t, int index) {
        if (counts == elements.length) {
            resize(2 * elements.length);
        }
        
        // 先把index索引处的元素以及后面的元素以此向后移动一位
        for (int i = counts; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        // 再把t元素插入到index索引处
        elements[index] = t;
        counts++;
    }
    
    // 删除指定位置i处的元素, 并返回该元素
    public T remove(int i) {
        // 记录索引i的值
        T element = elements[i];
        // 以此将后面的元素向前覆盖
        for (int index = i; index < counts - 1; index++) {
            elements[index] = elements[index + 1];
        }
        counts--;
        
        if (counts < elements.length / 4) {
            resize(elements.length / 2);
        }
        
        return element;
    }
    
    // 查找t元素第一次出现的位置
    public int indexOf(T t) {
        for (int i = 0; i < counts - 1; i++) {
            if (elements[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }
    
    // 根据参数 newSize, 重置 elements 的大小
    public void resize(int newSize) {
        // 定义一个临时数据, 指向原数组
        T[] temp = elements;
        // 创建新数组
        elements = ((T[]) new Object[newSize]);
        // 把原数组的数据拷贝到新的数组即可
        for (int i = 0; i < counts; i++) {
            elements[i] = temp[i];
        }
    }

    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }
    
    private class SIterator implements Iterator {
        private int cursor;

        public SIterator() {
            this.cursor = 0;
        }

        @Override
        public boolean hasNext() {
            return cursor < counts;
        }

        @Override
        public Object next() {
            return elements[cursor++];
        }
    }
}
